1. Field of the Invention
The invention relates generally to shift-type buffer systems and methods. More particularly, the invention relates to systems and methods for increasing the efficiency of processing data entries through a high-speed, shift-type buffer.
2. Related Art
Memory buffers are often used in digital circuits. Memory buffers can, for example, serve as temporary holding areas for data in transit from one device to another. Communicating devices often process data asynchronously, or at different rates. As a result, if one device is ready to transmit data and the receiving device is not yet ready to receive the data, the data is stored temporarily in the buffer connecting the devices until the receiving device is ready to accept the data. Communication between the devices could be difficult, inefficient, or even impossible without intermediate buffers.
One of the most common types of buffer is a first-in-first-out (FIFO). In a FIFO-type buffer, data entries exit/retire from the buffer in the order the data entries entered the buffer. A common implementation of a FIFO uses a read and a write pointer to monitor which data entry has just entered the buffer and which data entry is the oldest and will be the next to exit the buffer. As data entries enter and exit the buffer, the write and read pointers move in a cyclical manner to indicate the new incoming data entry and the next outgoing data entry.
The use of the read and write pointers allows implementation of a FIFO without requiring data entries to be moved from one location to another in the buffer. The use of read and write pointers, however, typically requires that that the data entry entering the buffer be made available to all the buffer locations. The write pointer then determines which location is enabled to store the data entry. Accordingly, the single data entry input to the buffer must be distributed, or fanned-out, in order for the single input to be made available to all the buffer locations. The fan-out circuitry may be deep and may require multiple clock cycles to propagate the input data, especially for a buffer with a large number of locations. Thus, read/write pointer FIFOs may not be suitable for applications where timing is critical, such as is the case with buffers used with high-speed processors.
Where timing is critical, a shift-type buffer may be used. In a shift-type buffer, data entries are initially stored in a first buffer location. As new data entries are ready to enter the buffer, the existing data entries are shifted through successive buffer locations to provide space for the new data entries. Although shift-type buffers allow new entries to be registered in the buffer more quickly than read/write pointer FIFOs, data entries in the buffer are continually required to shift/advance to new locations as new data entries enter the buffer.
Typically, a data entry exits the buffer if certain exit conditions are met. As digital circuits and devices become more complex, the time required to evaluate the exit conditions for data entries significantly increases. Moreover, additional time may be required in selecting the data entries that meet the exit conditions and removing the appropriate entries from the buffer. In some systems, the data is required to be encoded or processed. As a result, the time required for a data entry to exit the buffer may be significantly higher than the time required for a data entry to be registered in the buffer. For example, only one clock cycle may be required for a data entry to enter the buffer, but it may take two or more clock cycles to evaluate the exit conditions for a data entry to exit the buffer.
Conventionally, when it takes multiple cycles to evaluate the exit conditions and subsequently removed an entry from the buffer, it is necessary to delay the storing of any new entries in the buffer. This is because it is necessary to remove one of the existing entries in order to make space for the new entry. Thus, if it takes two cycles to remove an entry, an entry that is waiting to be stored in the buffer must also wait two or more cycles before it can be stored in the buffer. These delays decrease the efficiency with which the buffer operates.
It would therefore be desirable to provide systems and methods to avoid delays in processing buffer entries, particularly the delays that result from multiple-cycle evaluation of exit conditions and which cause the storing of new buffer entries to be delayed.